package listbyorder.access101_200.test115;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/8 9:09
 */
public class Solution3 {

    // 方法三————动态规划优化
    public int numDistinct(String s, String t) {
        if (s.length() < t.length()) return 0;
        int lens = s.length();
        int lent = t.length();
        int[][] dp = new int[lens + 1][lent + 1];
        for (int i = lens; i >= 0; i--) {
            for (int j = lent; j >= 0; j--) {
                if (j == lent) {
                    dp[i][j] = 1;
                } else if (lens - i < lent - j) {
                    continue;
                } else if (s.charAt(i) == t.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }
}
